package iorichina.hellojava.hellosample.monthly_rabbit_count;

///一、题目描述
//有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子。
//
//例如：假设一只兔子第3个月出生，那么它第5个月开始会每个月生一只兔子。
//
//一月的时候有一只兔子，假如兔子都不死，问第n个月的兔子总数为多少？
//
//数据范围：输入满足 1 \le n \le 31 \1≤n≤31
//
//二、输入描述
//输入一个int型整数表示第n个月。
//
//三、输出描述
//输出对应的兔子总数。
//
//四、测试用例
//测试用例1
//1、输入
//4
//
//2、输出
//3
//
//3、说明
//第4个月有3只兔子，1只初始兔子和2只新生兔子。
//
//测试用例2
//1、输入
//10
//
//2、输出
//55
//
//3、说明
//第10个月有55只兔子，随着每个月的兔子数量递增。
//
//五、解题思路
//老兔子+中兔子+新兔子（即所有老兔子生的）
//1:0+0+1=1
//2:0+1+0=1
//3:1+0+1=2=month(3-1)+month(3-2)
//4:1+1+1=3=month(4-1)+month(4-2)
//5:2+1+2=5=month(5-1)+month(5-2)
//6:3+2+3=8=month(6-1)+month(6-2)
//7:5+3+5=13=month(7-1)+month(7-2)
//8:8+5+8=21=month(8-1)+month(8-2)
//9:13+8+13=34=month(9-1)+month(9-2)
//10:21+13+21=55=month(10-1)+month(10-2)
//11:34+21+34=89=month(11-1)+month(11-2)

public class Solution {
    public int rabbitCount(int month) {
        if (month <= 0) {
            return 0;
        }
        if (month == 1) {
            return 1;
        }
        if (month == 2) {
            return 1;
        }
        //从第3个月开始，每个月的兔子数=老兔子+中兔子+新兔子（即所有老兔子生的）=上一个月兔子+上上个月兔子
        return rabbitCount(month - 1) + rabbitCount(month - 2);
    }
}
